package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC778 {
    public long startExecuteTime = System.currentTimeMillis();

    class Solution {
        public int swimInWater(int[][] grid) {
            List<Integer> lenList = new LinkedList<>();
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid.length; j++) {
                    lenList.add(grid[i][j]);
                }
            }

            Collections.sort(lenList);
            int left = 0, right = lenList.size() - 1, mid = 0;
            for (left = 0; left < lenList.size(); left++) {
                if (lenList.get(left) == grid[0][0]) break;
            }

            while (left < right) {
                mid = left + (right - left) / 2;
                if (!isMatch(lenList.get(mid), grid)) {
                    left = mid + 1;
                } else {
                    right = mid;  //二分搜索
                }
            }

            return lenList.get(left);
        }

        public boolean isMatch(int T, int[][] grid) {
            int N = grid.length;
            Set<Integer> seen = new HashSet();
            seen.add(0);
            int[] dr = new int[]{1, -1, 0, 0};
            int[] dc = new int[]{0, 0, 1, -1};

            Stack<Integer> stack = new Stack();
            stack.add(0);

            while (!stack.empty()) {
                int k = stack.pop();
                int r = k / N, c = k % N;
                if (r == N - 1 && c == N - 1) return true;

                for (int i = 0; i < 4; ++i) {
                    int cr = r + dr[i], cc = c + dc[i];
                    int ck = cr * N + cc;
                    if (0 <= cr && cr < N && 0 <= cc && cc < N
                            && !seen.contains(ck) && grid[cr][cc] <= T) {
                        stack.add(ck);
                        seen.add(ck);
                    }
                }
            }

            return false;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[][] arr = InputUtil.toDoubleIntegerArray("[[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]");
        System.out.println(solution.swimInWater(arr));
    }

    public static void main(String[] args) throws Exception {
        LC778 an = new LC778();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
